/********************************************************************************
 * Project Name		[JavaSE_Fundamentals]
 * File Name     	[Notes.java]
 * Creation Date 	[2015-01-01]
 * 
 * Copyright© ge.y.yang@gmail.com All Rights Reserved
 * 
 * Work hard, play harder, think big and keep fit
 ********************************************************************************/
package collections;

/**
 * @author 不落的太阳(Sean Yang aka ShortPeace)
 * @version 1.0
 * @since jdk 1.8
 * 
 */
public class Notes {

	public void list() {
		/**
		 * ArrayList<br/>
		 * <code>
		 * ArrayList是最常用的List实现类, 内部是通过数组实现的, 它允许对元素进行快速随机访问
		 * ArrayList大小不满足时会增加存储能力, 新长度为原长度的[1.5倍+1(jdk 1.6)]/[0.5倍(jdk 1.7)]
		 * ArrayList自增长的方式是将已有数组数据复制到新的存储空间中
		 * 向ArrayList的中间位置插入或者删除元素时, 需要对数组进行拷贝, 移动, 代价比较高[数组的缺点是每个元素之间不能含有空隙], 因此, 它适合随机查找和遍历, 不适合插入和删除
		 * </code><br/>
		 * 
		 * Vector<br/>
		 * <code>
		 * Vector与ArrayList一样, 也是通过数组实现的, 不同的是它支持线程的同步, 即同一时刻只有一个线程能够写Vector, 避免多线程同时写引起的不一致性
		 * 实现同步需要很高的花费, 因此, 访问它比访问ArrayList慢
		 * </code><br/>
		 * 
		 * LinkedList<br/>
		 * <code>
		 * LinkedList使用链表结构存储数据, 很适合数据的动态插入和删除, 随机访问和遍历速度比较慢
		 * 此外它还提供了List没有定义的方法, 专门用于操作表头和表尾元素, 可以当作堆栈, 队列和双向队列使用<br/>
		 * </code><br/>
		 * 
		 * 
		 * ArrayList和Vector采用数组实现, 在添加和插入时, 最好从表尾操作而不要从中间或表头开始, 以避免数组移动引起的开销
		 * <br/>
		 * 
		 * List拥有一个ListIterator, 支持双向遍历List, 而且能够在ListIterator位置插入和删除元素 <br/>
		 * 
		 * 堆栈类继承Vector, 它总是对列表的尾部数据进行操作, 采用了先进后出的策略, 自定义了插入, 查看和弹出元素三个方法<br/>
		 */
	}

	public void set() {
		/**
		 * Set不允许重复元素, 因此加入Set的Object必须定义equals()和hashCode()方法以确保对象的唯一性<br/>
		 * 
		 * HashSet<br/>
		 * <code>
		 * HashSet采用散列函数对元素进行排序, 是专门为快速查询而设计的. 存入HashSet的对象必须定义hashCode()
		 * HashSet底层是使用HashMap实现的, 当使用add方法将对象添加到Set当中时, 实际上是将该对象作为底层所维护的Map对象的key,而value则都是同一个Object对象
		 * 
		 * HashSet的实现原理
		 * 向HashSet添加元素时, HashSet会先调用元素的hashCode方法得到元素的哈希值, 然后通过元素的哈希值经过移位等运算就可以算出该元素在哈希表中的存储位置, 
		 * 如果算出元素存储的位置目前没有任何元素存储, 那么该元素可以直接存储到该位置上, 
		 * 如果算出该元素的存储位置目前已经存在有其他的元素了, 那么会调用该元素的equals方法与该位置的元素再比较一次, 
		 * 如果equals返回的是true, 那么该元素与这个位置上的元素就视为重复元素, 不允许添加, 如果equals方法返回的是false, 那么该元素允许添加
		 * </code><br/>
		 * 
		 * TreeSet采用红黑树的数据结构进行排序元素, 能保证元素的次序, 使用它可以从Set中提取有序的序列<br/>
		 * <code>
		 * 向TreeSet添加元素时如果元素本身具有自然顺序的特性, 那么按照元素自然顺序的特性进行排序存储
		 * 向TreeSet添加元素时如果元素本身没有自然顺序的特性, 那么该元素所属的类必须实现Comparable接口的compareTo(T o)方法
		 * 向TreeSet添加元素时如果元素本身没有自然顺序的特性, 且元素所属类也没有实现Comparable接口, 要在创建TreeSet时传入一个比较器
		 * 向TreeSet添加元素时如果元素本身没有自然顺序的特性, 且元素所属类已经实现了Comparable接口, 在创建TreeSet对象的时候也传入了比较器, 那么是以比较器的比较规则优先使用
		 * 如果比较元素的时候, compareTo方法返回的是0, 那该元素就被视为重复元素, 不允许添加
		 * </code><br/>
		 * 
		 * TreeSet与HashCode, equals方法是没有任何关系<br/>
		 * 
		 * LinkedHashSet内部使用散列以加快查询速度, 同时使用链表维护元素的插入的次序, 在使用迭代器遍历Set时,
		 * 结果会按元素插入的次序显示<br/>
		 */
	}

	public void map() {
		/**
		 * Map用于存储键值对, 不允许键重复, 值可以重复, 如果插入两个键值一样的记录, 那么后插入的记录会覆盖先插入的记录<br/>
		 * 
		 * HashMap<br/>
		 * <code>
		 * HashMap是一个最常用的Map, 它根据键的hashCode值存储数据, 根据键可以直接获取它的值, 具有很快的访问速度
		 * HashMap底层维护了一个数组, 向HashMap中所放置的对象实际上是存储在该数组当中
		 * HashMap最多只允许一条记录的键为null, 允许多条记录的值为null
		 * HashMap不支持线程的同步, 即任一时刻可以有多个线程同时写HashMap, 可能会导致数据的不一致, 如果需要同步, 可以用Collections.synchronizedMap(HashMap map)方法使HashMap具有同步的能力
		 * 
		 * HashSet的实现原理
		 * 当向HashMap中put一对键值时, 它会根据key的hashCode值计算出一个位置, 该位置就是此对象准备往数组中存放的位置, 
		 * 如果该位置没有对象存在, 就将此对象直接放进数组当中; 如果该位置已经有对象存在了, 则顺着此存在的对象的链开始寻找
		 * [Entry类有一个Entry类型的next成员变量, 指向了该对象的下一个对象], 如果此链上有对象的话, 再去使用equals方法进行比较, 
		 * 如果对此链上的某个对象的equals方法比较为false, 则将该对象放到数组当中, 然后将数组中该位置以前存在的那个对象链接到此对象的后面
		 * </code><br/>
		 * 
		 * Hashtable与HashMap类似, 不同的是: 它不允许记录的键或者值为空; 它支持线程的同步,
		 * 即任一时刻只有一个线程能写Hashtable, 然而, 这也导致了Hashtable在写入时会比较慢<br/>
		 * 
		 * LinkedHashMap保存了记录的插入顺序, 在用Iterator遍历LinkedHashMap时, 先得到的记录肯定是先插入的,
		 * 在遍历的时候会比HashMap慢, 其键和值均可以为null<br/>
		 * 
		 * TreeMap能够把它保存的记录根据键排序, 默认是按升序排序, 也可以指定排序的比较器; 当用Iterator遍历TreeMap时,
		 * 得到的记录是排过序的, 其键值或均不可以为null<br/>
		 */
	}
}
